import java.util.ArrayDeque;
import java.util.Deque;

public class Solution239 {
    public int[] maxSlidingWindow(int[] nums,int k){
        MonotonicQueue window = new MonotonicQueue();
        int[] res = new int[nums.length - k + 1];
        int resIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            if(i < k - 1){
                window.push(nums[i]);
            }else {
                window.push(nums[i]);
                res[resIndex++] = window.max();
                window.pop(nums[i-k+1]);
            }
        }
        return res;
    }
}
class MonotonicQueue{
    private Deque<Integer> data;
    public MonotonicQueue(){
        data = new ArrayDeque<>();
    }
    public void push(int n){
        while (!data.isEmpty() && data.peekLast() < n){
            data.pollLast();
        }
        data.offerLast(n);
    }
    public int max(){
        return data.peekFirst();
    }
    public void pop(int n){
        if(!data.isEmpty() && data.peekFirst() == n){
            data.pollFirst();
        }
    }
}
